home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
The Atari Compendium
/
The Atari Compendium (Toad Computers) (1994).iso
/
files
/
umich
/
utils
/
sort.arc
/
sort.c
< prev
next >
Wrap
C/C++ Source or Header
|
1989-03-30
|
18KB
|
432 lines
/******************************************************************************
* *
* sort.c version 1.0 of 22 Januari 1989 (C) L.J.M. de Wit 1989 *
* *
* This software may be used and distributed freely if not used commercially *
* and the originator (me) is mentioned in the source (just leave this 9 line *
* header intact). *
* *
******************************************************************************
*
* sort.c: basic sort functions
*/
#include <stdio.h>
#include <osbind.h>
#include "sortmain.h"
#include "sortfile.h"
#define LINELEN 256 /* Max length of input lines*/
#define MAXNAMLEN 80 /* Max length of filename */
#define MAXMERGE 8 /* Max. no of files to be */
/* simultaneously merged */
static int (*cmp)(); /* Ptr to compare function */
static void sortsub(), /* Recursive quicksort */
merge(); /* Merge sorted files */
static void tempname(); /* Creates temporary name */
static int isort(); /* Initial sort of file(s) */
static char tmpdir[MAXNAMLEN]; /* Name of temp files dir */
static char insave[2][LINELEN]; /* Used by unique */
void settemp(tempdir) /* Sets the temp files dir */
char *tempdir;
{
strcpy(tmpdir,tempdir);
}
static void sortsub(sbase,stop) /* Sort the pointers */
char **sbase, **stop; /* between sbase and stop */
{
register char **base = sbase, /* All below base and above */
**top = stop, /* top is kept sorted with */
**mid, /* respect to element *mid */
*tmp; /* For swapping values */
register long compfunc = (long)cmp; /* Kludge to use extra reg. */
#define CMP (*(int (*)())compfunc) /* Replaces (*cmp) */
mid = base + ((top - base) >> 1); /* Choose pivot */
--top;
if (top - base >= 6) { /* Make sure pivot mid value*/
if (CMP(*base,*mid) > 0) {
if (CMP(*mid,*top) <= 0) {
if (CMP(*base,*top) > 0) {
tmp = *mid; /* Swap *mid and *top */
*mid = *top;
*top = tmp;
} else {
tmp = *mid; /* Swap *base and *mid */
*mid = *base;
*base = tmp;
}
}
} else if (CMP(*mid,*top) > 0) {
tmp = *mid; /* Swap *mid and *top */
*mid = *top;
*top = tmp;
}
} else { /* <= 6 elts: use bubblesort*/
for ( ; base < top; --top) {
for (mid = base; mid < top; mid++) {
if (CMP(*mid,mid[1]) > 0) {
tmp = *mid; *mid = mid[1]; mid[1] = tmp;
}
}
}
return; /* and return ... */
}
do {
for ( ; base < mid && CMP(*base,*mid) <= 0; base++) ;
for ( ; top > mid && CMP(*mid,*top) <= 0; --top) ;
if (base < top) {
tmp = *base; *base = *top; *top = tmp; /* Swap *base and *top */
if (mid == top) {
mid = base;
--top;
} else if (mid == base) {
mid = top;
base++;
}
}
} while (base < top); /* Until all sorted to *mid */
if (mid - sbase > 1) { /* Sort lower half if >1 elt*/
sortsub(sbase,mid);
}
if (stop - mid > 1) { /* Sort upper half if >1 elt*/
sortsub(mid,stop);
}
}
static void merge(infnames,level,
startno,nmerge,outfname) /* Merge sorted input files */
char **infnames; /* Input file names array */
int level, /* No. of times merged */
startno, /* Sequence no. within level*/
nmerge; /* No. of files to merge */
char *outfname; /* File to be written to */
{
static char *inbuf[MAXMERGE]; /* (0)Ptrs to input buffers */
static FILE *infp[MAXMERGE], *outfp; /* Input and output FILE *'s*/
char namebuf[MAXNAMLEN]; /* To store temp file names */
char *nameptr;
int cur, /* Number of current file */
i, j,
nbusy = 0, /* # of input files in use */
tmp;
int order[MAXMERGE]; /* Ordering of file numbers */
char *s;
long avail;
avail = (Malloc(-1) - 20480) & ~1; /* Get free - 20K */
avail /= nmerge + 1;
avail -= avail % 2048;
if (outfname == (char *)0) {
outfp = stdout; /* stdout is default */
} else {
outfp = fopen(outfname,"w");
if (outfp == (FILE *)0) {
error("%s: cannot open for write\n",outfname);
}
}
if ((s = (char *)Malloc(avail)) == (char *)-1) { /* Grab it */
error("memory allocation failed\n",(char *)0);
}
setbuffer(outfp,s,avail);
if (level < 0) {
if (*infnames != (char *)0) {
for (i = 0; i < startno; i++) {
infnames++;
}
}
}
for (i = 0; i < nmerge; i++) { /* Open each input file */
if (level < 0) {
nameptr = *infnames++;
} else {
tempname(namebuf,level,startno+i);
nameptr = namebuf;
}
if (nameptr == (char *)0 || !strcmp(nameptr,"-")) {
infp[i] = stdin; /* stdin is default */
} else {
infp[i] = fopen(nameptr,"r");
if (infp[i] == (FILE *)0) {
error("%s: cannot open for read\n",nameptr);
}
}
if ((s = (char *)Malloc(avail)) == (char *)-1) { /* Grab it */
error("memory allocation failed\n",(char *)0);
}
setbuffer(infp[i],s,avail);
if (inbuf[i] == (char *)0) { /* Possibly allocate buffer */
if ((inbuf[i] = (char *)malloc(LINELEN)) == (char *)0) {
error("memory allocation failed\n",(char *)0);
}
}
if (fgets(inbuf[i],LINELEN,infp[i]) != (char *)0) { /* Read 1st line*/
order[nbusy++] = i; /* Enter its seq no. */
for (j = nbusy - 1; j >= 1 && /* Put in place in order */
(*cmp)(inbuf[order[j-1]],inbuf[order[j]]) > 0; --j) {
tmp = order[j-1]; order[j-1] = order[j]; order[j] = tmp;
}
}
}
if ((options & UNIQUE) && nbusy > 0) {
insave[0][0] = inbuf[order[0]][0] + 1; /* Force difference */
}
while (nbusy > 0) {
cur = order[0]; /* No. of lowest ordered */
if (options & UNIQUE) {
if ((*cmp)(inbuf[cur],insave[0])) { /* Differs from previous one*/
fputs(inbuf[cur],outfp); /* Write out lowest ordered */
strcpy(insave[0],inbuf[cur]);
}
} else {
fputs(inbuf[cur],outfp); /* Write out lowest ordered */